题目分析

这个题目简单的原因不是因为算法简单，而是数据量简单。使用暴力法都可以通过，小伙伴们想一想如何优化？

暴力法

思路非常简单，遍历每一个数，对于prices[i]，枚举j，找到满足条件的j。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> res;
        for (int i = 0; i < prices.size(); i++) {
            int diff = 0;
            for (int j = i + 1; j < prices.size(); j++) {
                if (prices[j] <= prices[i]) { diff = prices[j]; break; }
            }
            res.push_back(prices[i] - diff);
        }
        return res;
    }
};

单调栈

暴力法我们每次都要从i+1开始向后比较，如果样例是2，3，4，5，1，那么2后面小于等于2的数是1，3后面小于等于3的数是1，这样会浪费大量的时间。

我们可以维护一个递增的栈，当出现一个较小的数k时，我们依次弹出栈顶元素直到栈为空或者栈顶元素小于k。那么弹出的元素，都满足大于等于k，而且k是第一个满足条件的数，因此我们让这些数-k即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> s;
        for (int i = 0; i < prices.size(); i++) {
            while (!s.empty() && prices[i] <= prices[s.back()]) {
                prices[s.back()] -= prices[i];
                s.pop_back();
            }
            s.push_back(i);
        }
        return prices;
    }
};

刷题总结

有几类问题是小伙伴们必须必须掌握的，在这里进行一个列举，动态规划，双指针，单调栈，深搜，广搜，哈希表，递归，排序，堆，贪心。这是最最重要的一些算法类型，希望小伙伴们可以有针对性的进行训练。